
'''
双向链表是根据结点来实现的，
每个结点存储数据和下一个结点的位置，上一个结点的位置。
'''

class Node(object):
    '''定义结点类，主要通过传入值来生成一个结点，该类对外隐藏'''
    def __init__(self, data):
        self.item = data
        self.next = None
        self.prev = None

class DoubleLinkList():
    '''创建单链表，只要单链表的头指向结点的位置就行'''
    def __init__(self):
        self._head = None

    def add(self,data):
        '''头部增加数据'''
        node = Node(data)
        if self._head is not None:
            node.next = self._head
            self._head.prev = node
        else:
            node.next = None
        self._head = node

    def append(self,data):
        '''尾部增加数据'''
        if self._head is None:
            self.add(data)
            return
        node = Node(data)
        # 需要先找到尾部
        cur = self._head
        while cur.next is not None:
            cur = cur.next
        # node.next = None
        node.prev = cur
        cur.next = node

    def insert(self,pos,data):
        # 指定位置增加元素
        # 找到该位置
        if pos <= 0:
            # 默认在头部插入
            self.add(data)
        elif pos >= self.length()-1:
            # 在尾部插入
            self.append(data)
        else:
            # 在中间位置
            cur_pos = 0
            cur = self._head
            # pre = None
            while cur_pos < pos:
                cur_pos += 1
                # pre  = cur
                cur = cur.next

            #
            # cur.next
            node = Node(data)
            node.prev = cur
            node.next = cur.next
            cur.next.prev = node
            cur.next = node


    def delete(self,data):
        '''删除一个值'''
        cur = self._head
        # pre = None
        is_delete = False
        while cur is not None:
            if cur.item == data:
                # 找到删除
                # 如果被删除的是第一个值
                if cur.prev is None:
                    self._head = cur.next
                else:
                    cur.prev.next = cur.next
                is_delete = True
                break

            cur = cur.next

        if is_delete is False:
            print('该元素不存在')

    def search(self,data):
        '''查找该结点是否存在'''
        cur = self._head
        is_delete = False
        while cur is not None:
            if cur.item == data:
                is_delete = True
                print('该元素存在')
                break
            cur = cur.next

        if is_delete is False:
            print('该元素不存在')


    def travel(self):
        '''遍历整个单链表'''
        cur = self._head
        # if cur is None:
        #     return None

        while cur is not None:
            print(cur.item,end=' ')
            cur = cur.next
        print('')

    def length(self):
        '''链表长度'''
        _length = 0
        cur = self._head
        while cur is not None:
            _length += 1
            cur = cur.next
        return _length


if __name__ == '__main__':
    single = DoubleLinkList()
    single.travel()
    print(single.length())  # 0

    single.add('aaa')
    single.add('bbb')
    single.add('ccc')
    single.travel() #ccc bbb aaa
    print(single.length())  # 3


    single.append('dddd')
    single.append('eeee')
    single.travel()  #ccc bbb aaa dddd eeee

    single2 = DoubleLinkList()
    single2.append('aaaa')
    single2.append('aaaa')
    single2.travel()  #aaaa aaaa

    single.delete('ccc') # 删除第一个
    single.travel()  # bbb aaa dddd eeee
    single.delete('aaa')  # 删除中间一个
    single.travel()  # bbb  dddd eeee
    single.delete('eeee') # 删除最后一个
    single.travel() # bbb dddd
    single.delete('xxxxxxx') # 删除不存在的
    single.travel() # bbb dddd

    single.insert(-1,'aaaa') # 在负值中插入
    single.travel() # aaaa bbb dddd
    single.insert(0,'bbbb')
    single.travel() # bbbb aaaa bbb dddd
    single.insert(1,'cccc')
    single.travel() #bbbb cccc aaaa bbb dddd
    single.insert(5,'gggg')
    single.travel() #bbbb cccc aaaa bbb dddd gggg
    single.insert(8,'kkkk')
    single.travel() #bbbb cccc aaaa bbb dddd gggg kkkk

    single.search('bbbb')
    single.search('jjjj')
